The core of Dijkstra's algorithm relies on a greedy strategy to confirm the shortest path to one vertex at a time.

  • The core idea is to maintain two sets of vertices: the Visited Set (finalized paths) and the Unvisited Set (paths still being calculated).
  • The Visited Set contains vertices $v$ for which the shortest distance $d[v]$ from the source is known and guaranteed.
  • The Greedy Strategy dictates the selection process from the Unvisited Set.
  • At every step, the algorithm selects the unvisited vertex $u$ that currently has the smallest known distance $d[u]$ from the source.
  • This selected node $u$ is then "visited" (moved to the Visited Set), confirming $d[u]$ as the final shortest path.
  • Why? Because all edge weights $w(u, v)$ are non-negative, any future path to $u$ must be longer than or equal to the current path, guaranteeing the greedy choice is optimal.
Formal Definition: Greedy Choice

Term: Greedy Choice Property

Always select the unvisited vertex $u$ with the minimum known distance $d[u]$. Once selected, this distance is final and will never change.

This property holds true only when all edge weights $w(u, v)$ are non-negative.